/* 241. 为运算表达式设计优先级 */
/**
 * @param {string} expression
 * @return {number[]}
 */

/*
    分治算法:
    按照运算符进行分割，给每个运算符的左右两部分加括号
*/
const memo = new Map()
var diffWaysToCompute = function (expression) {
	/* 避免重复计算 */
	if (memo.has(expression)) return memo.get(expression)
	const res = []
	for (let i = 0; i < expression.length; i++) {
		const c = expression.charAt(i)
		const operators = ['*', '+', '-']
		// 扫描运算符
		if (operators.includes(c)) {
			/* 分 */
			const left = diffWaysToCompute(expression.slice(0, i))
			const right = diffWaysToCompute(expression.slice(i + 1))
			/* 
                治
                通过子问题的结果，合成原问题的结果 
            */
			for (const a of left) {
				for (const b of right) {
					switch (c) {
						case '*':
							res.push(a * b)
							break
						case '+':
							res.push(a + b)
							break
						case '-':
							res.push(a - b)
							break
					}
				}
			}
		}
	}
	/* 
        base  case 
        如果res为空,说明算式是一个数字，没有运算符
    */
	if (!res.length) {
		res.push(parseInt(expression))
	}
	memo.set(expression, res)
	return res
}
const res = diffWaysToCompute('2-1-1')
console.log('diffWaysToCompute :>>', res)
